package com.kehao.newcoder;

import java.util.ArrayList;

public class NC8Solution {
    private class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;

        public TreeNode(int val) {
            this.val = val;
        }
    }

    ArrayList<ArrayList<Integer>> result;
    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root, int expectNumber) {
        result = new ArrayList<>();
        dfs(root,expectNumber,0,new ArrayList<>());
        return result;
    }

    private void dfs(TreeNode root, int expectNumber, int num,ArrayList<Integer> list) {
        if(root==null){
            return;
        }
        if(root.left==null&&root.right==null){
            if(num+root.val == expectNumber){
                list.add(root.val);
                result.add(new ArrayList<>(list));
                list.remove(list.size()-1);
            }
            return;
        }
        if(root.left!=null){
            list.add(root.val);
            dfs(root.left,expectNumber,num+root.val,list);
            list.remove(list.size()-1);
        }
        if(root.right!=null){
            list.add(root.val);
            dfs(root.right,expectNumber,num+root.val,list);
            list.remove(list.size()-1);
        }

    }
}
